<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<title>STX B+ Tree Template Classes: stx/btree_map.h Source File</title>

<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css" />

<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { searchBox.OnSelectItem(0); });
</script>

</head>
<body>
<div id="top"><!-- do not remove this div! -->


<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  
  
  <td style="padding-left: 0.5em;">
   <div id="projectname">STX B+ Tree Template Classes
   &#160;<span id="projectnumber">0.9</span>
   </div>
   
  </td>
  
  
  
 </tr>
 </tbody>
</table>
</div>

<!-- Generated by Doxygen 1.7.6.1 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li><a href="namespaces.html"><span>Namespaces</span></a></li>
      <li><a href="annotated.html"><span>Classes</span></a></li>
      <li class="current"><a href="files.html"><span>Files</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
      </li>
    </ul>
  </div>
  <div id="navrow2" class="tabs2">
    <ul class="tablist">
      <li><a href="files.html"><span>File&#160;List</span></a></li>
      <li><a href="globals.html"><span>File&#160;Members</span></a></li>
    </ul>
  </div>
</div>
<div class="header">
  <div class="headertitle">
<div class="title">stx/btree_map.h</div>  </div>
</div><!--header-->
<div class="contents">
<a href="a00028.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/** \file btree_map.h</span>
<a name="l00002"></a>00002 <span class="comment"> * Contains the specialized B+ tree template class btree_map</span>
<a name="l00003"></a>00003 <span class="comment"> */</span>
<a name="l00004"></a>00004 
<a name="l00005"></a>00005 <span class="comment">/*</span>
<a name="l00006"></a>00006 <span class="comment"> * STX B+ Tree Template Classes v0.9</span>
<a name="l00007"></a>00007 <span class="comment"> * Copyright (C) 2008-2013 Timo Bingmann &lt;tb@panthema.net&gt;</span>
<a name="l00008"></a>00008 <span class="comment"> *</span>
<a name="l00009"></a>00009 <span class="comment"> * Boost Software License - Version 1.0 - August 17th, 2003</span>
<a name="l00010"></a>00010 <span class="comment"> *</span>
<a name="l00011"></a>00011 <span class="comment"> * Permission is hereby granted, free of charge, to any person or organization</span>
<a name="l00012"></a>00012 <span class="comment"> * obtaining a copy of the software and accompanying documentation covered by</span>
<a name="l00013"></a>00013 <span class="comment"> * this license (the &quot;Software&quot;) to use, reproduce, display, distribute,</span>
<a name="l00014"></a>00014 <span class="comment"> * execute, and transmit the Software, and to prepare derivative works of the</span>
<a name="l00015"></a>00015 <span class="comment"> * Software, and to permit third-parties to whom the Software is furnished to</span>
<a name="l00016"></a>00016 <span class="comment"> * do so, all subject to the following:</span>
<a name="l00017"></a>00017 <span class="comment"> *</span>
<a name="l00018"></a>00018 <span class="comment"> * The copyright notices in the Software and this entire statement, including</span>
<a name="l00019"></a>00019 <span class="comment"> * the above license grant, this restriction and the following disclaimer, must</span>
<a name="l00020"></a>00020 <span class="comment"> * be included in all copies of the Software, in whole or in part, and all</span>
<a name="l00021"></a>00021 <span class="comment"> * derivative works of the Software, unless such copies or derivative works are</span>
<a name="l00022"></a>00022 <span class="comment"> * solely in the form of machine-executable object code generated by a source</span>
<a name="l00023"></a>00023 <span class="comment"> * language processor.</span>
<a name="l00024"></a>00024 <span class="comment"> *</span>
<a name="l00025"></a>00025 <span class="comment"> * THE SOFTWARE IS PROVIDED &quot;AS IS&quot;, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR</span>
<a name="l00026"></a>00026 <span class="comment"> * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,</span>
<a name="l00027"></a>00027 <span class="comment"> * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT</span>
<a name="l00028"></a>00028 <span class="comment"> * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE</span>
<a name="l00029"></a>00029 <span class="comment"> * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,</span>
<a name="l00030"></a>00030 <span class="comment"> * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER</span>
<a name="l00031"></a>00031 <span class="comment"> * DEALINGS IN THE SOFTWARE.</span>
<a name="l00032"></a>00032 <span class="comment"> */</span>
<a name="l00033"></a>00033 
<a name="l00034"></a>00034 <span class="preprocessor">#ifndef _STX_BTREE_MAP_H_</span>
<a name="l00035"></a>00035 <span class="preprocessor"></span><span class="preprocessor">#define _STX_BTREE_MAP_H_</span>
<a name="l00036"></a>00036 <span class="preprocessor"></span>
<a name="l00037"></a>00037 <span class="preprocessor">#include &lt;<a class="code" href="a00026.html" title="Contains the main B+ tree implementation template class btree.">stx/btree.h</a>&gt;</span>
<a name="l00038"></a>00038 
<a name="l00039"></a>00039 <span class="keyword">namespace </span>stx {
<a name="l00040"></a>00040 <span class="comment"></span>
<a name="l00041"></a>00041 <span class="comment">/** @brief Specialized B+ tree template class implementing STL&#39;s map container.</span>
<a name="l00042"></a>00042 <span class="comment"> *</span>
<a name="l00043"></a>00043 <span class="comment"> * Implements the STL map using a B+ tree. It can be used as a drop-in</span>
<a name="l00044"></a>00044 <span class="comment"> * replacement for std::map. Not all asymptotic time requirements are met in</span>
<a name="l00045"></a>00045 <span class="comment"> * theory. The class has a traits class defining B+ tree properties like slots</span>
<a name="l00046"></a>00046 <span class="comment"> * and self-verification. Furthermore an allocator can be specified for tree</span>
<a name="l00047"></a>00047 <span class="comment"> * nodes.</span>
<a name="l00048"></a>00048 <span class="comment"> *</span>
<a name="l00049"></a>00049 <span class="comment"> * Most noteworthy difference to the default red-black implementation of</span>
<a name="l00050"></a>00050 <span class="comment"> * std::map is that the B+ tree does not hold key and data pair together in</span>
<a name="l00051"></a>00051 <span class="comment"> * memory. Instead each B+ tree node has two arrays of keys and data</span>
<a name="l00052"></a>00052 <span class="comment"> * values. This design directly generates many problems in implementing the</span>
<a name="l00053"></a>00053 <span class="comment"> * iterator&#39;s operator&#39;s which return value_type composition pairs.</span>
<a name="l00054"></a>00054 <span class="comment"> */</span>
<a name="l00055"></a>00055 <span class="keyword">template</span> &lt;<span class="keyword">typename</span> _Key, <span class="keyword">typename</span> _Data,
<a name="l00056"></a>00056           <span class="keyword">typename</span> _Compare = std::less&lt;_Key&gt;,
<a name="l00057"></a>00057           <span class="keyword">typename</span> _Traits = btree_default_map_traits&lt;_Key, _Data&gt;,
<a name="l00058"></a>00058           <span class="keyword">typename</span> _Alloc = std::allocator&lt;std::pair&lt;_Key, _Data&gt; &gt; &gt;
<a name="l00059"></a><a class="code" href="a00004.html">00059</a> <span class="keyword">class </span><a class="code" href="a00004.html" title="Specialized B+ tree template class implementing STL&#39;s map container.">btree_map</a>
<a name="l00060"></a>00060 {
<a name="l00061"></a>00061 <span class="keyword">public</span>:
<a name="l00062"></a>00062     <span class="comment">// *** Template Parameter Types</span>
<a name="l00063"></a>00063 <span class="comment"></span>
<a name="l00064"></a>00064 <span class="comment">    /// First template parameter: The key type of the btree. This is stored in</span>
<a name="l00065"></a>00065 <span class="comment">    /// inner nodes and leaves</span>
<a name="l00066"></a><a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92">00066</a> <span class="comment"></span>    <span class="keyword">typedef</span> _Key                        <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a>;
<a name="l00067"></a>00067 <span class="comment"></span>
<a name="l00068"></a>00068 <span class="comment">    /// Second template parameter: The data type associated with each</span>
<a name="l00069"></a>00069 <span class="comment">    /// key. Stored in the B+ tree&#39;s leaves</span>
<a name="l00070"></a><a class="code" href="a00004.html#a76d4185d0ff8a2b0fbb572aad2ee93bb">00070</a> <span class="comment"></span>    <span class="keyword">typedef</span> _Data                       <a class="code" href="a00004.html#a76d4185d0ff8a2b0fbb572aad2ee93bb" title="Second template parameter: The data type associated with each key.">data_type</a>;
<a name="l00071"></a>00071 <span class="comment"></span>
<a name="l00072"></a>00072 <span class="comment">    /// Third template parameter: Key comparison function object</span>
<a name="l00073"></a><a class="code" href="a00004.html#a7c428c8ee8f8ec5041739f6bb55089c1">00073</a> <span class="comment"></span>    <span class="keyword">typedef</span> _Compare                    <a class="code" href="a00004.html#a7c428c8ee8f8ec5041739f6bb55089c1" title="Third template parameter: Key comparison function object.">key_compare</a>;
<a name="l00074"></a>00074 <span class="comment"></span>
<a name="l00075"></a>00075 <span class="comment">    /// Fourth template parameter: Traits object used to define more parameters</span>
<a name="l00076"></a>00076 <span class="comment">    /// of the B+ tree</span>
<a name="l00077"></a><a class="code" href="a00004.html#ae6754ad8a27ece08ef50350eb6848e77">00077</a> <span class="comment"></span>    <span class="keyword">typedef</span> _Traits                     <a class="code" href="a00004.html#ae6754ad8a27ece08ef50350eb6848e77" title="Fourth template parameter: Traits object used to define more parameters of the B+ tree...">traits</a>;
<a name="l00078"></a>00078 <span class="comment"></span>
<a name="l00079"></a>00079 <span class="comment">    /// Fifth template parameter: STL allocator</span>
<a name="l00080"></a><a class="code" href="a00004.html#a5d0f64823a786b0652038b8702ae5343">00080</a> <span class="comment"></span>    <span class="keyword">typedef</span> _Alloc                      <a class="code" href="a00004.html#a5d0f64823a786b0652038b8702ae5343" title="Fifth template parameter: STL allocator.">allocator_type</a>;
<a name="l00081"></a>00081 
<a name="l00082"></a>00082     <span class="comment">// The macro BTREE_FRIENDS can be used by outside class to access the B+</span>
<a name="l00083"></a>00083     <span class="comment">// tree internals. This was added for wxBTreeDemo to be able to draw the</span>
<a name="l00084"></a>00084     <span class="comment">// tree.</span>
<a name="l00085"></a>00085     <a class="code" href="a00026.html#aec07a93b351ce398f789007a441a4320" title="The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.">BTREE_FRIENDS</a>
<a name="l00086"></a>00086 
<a name="l00087"></a>00087 <span class="keyword">public</span>:
<a name="l00088"></a>00088     <span class="comment">// *** Constructed Types</span>
<a name="l00089"></a>00089 <span class="comment"></span>
<a name="l00090"></a>00090 <span class="comment">    /// Typedef of our own type</span>
<a name="l00091"></a><a class="code" href="a00004.html#a85feee85c59b090041a84a7641574397">00091</a> <span class="comment"></span>    <span class="keyword">typedef</span> <a class="code" href="a00004.html" title="Specialized B+ tree template class implementing STL&#39;s map container.">btree_map&lt;key_type, data_type, key_compare, traits, allocator_type&gt;</a> <span class="keyword">self</span>;
<a name="l00092"></a>00092 <span class="comment"></span>
<a name="l00093"></a>00093 <span class="comment">    /// Construct the STL-required value_type as a composition pair of key and</span>
<a name="l00094"></a>00094 <span class="comment">    /// data types</span>
<a name="l00095"></a><a class="code" href="a00004.html#abdb0354081cf05ed114f76b09630001e">00095</a> <span class="comment"></span>    <span class="keyword">typedef</span> std::pair&lt;key_type, data_type&gt;      <a class="code" href="a00004.html#abdb0354081cf05ed114f76b09630001e" title="Construct the STL-required value_type as a composition pair of key and data types.">value_type</a>;
<a name="l00096"></a>00096 <span class="comment"></span>
<a name="l00097"></a>00097 <span class="comment">    /// Implementation type of the btree_base</span>
<a name="l00098"></a>00098 <span class="comment"></span>    <span class="keyword">typedef</span> <a class="code" href="a00001.html" title="Basic class implementing a base B+ tree data structure in memory.">stx::btree</a>&lt;<a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a>, <a class="code" href="a00004.html#a76d4185d0ff8a2b0fbb572aad2ee93bb" title="Second template parameter: The data type associated with each key.">data_type</a>, <a class="code" href="a00004.html#abdb0354081cf05ed114f76b09630001e" title="Construct the STL-required value_type as a composition pair of key and data types.">value_type</a>, <a class="code" href="a00004.html#a7c428c8ee8f8ec5041739f6bb55089c1" title="Third template parameter: Key comparison function object.">key_compare</a>,
<a name="l00099"></a><a class="code" href="a00004.html#aef5dfa6e8d4286e56ea8be50a0c020a7">00099</a>                        <a class="code" href="a00004.html#ae6754ad8a27ece08ef50350eb6848e77" title="Fourth template parameter: Traits object used to define more parameters of the B+ tree...">traits</a>, <span class="keyword">false</span>, <a class="code" href="a00004.html#a5d0f64823a786b0652038b8702ae5343" title="Fifth template parameter: STL allocator.">allocator_type</a>, <span class="keyword">false</span>&gt; <a class="code" href="a00004.html#aef5dfa6e8d4286e56ea8be50a0c020a7" title="Implementation type of the btree_base.">btree_impl</a>;
<a name="l00100"></a>00100 <span class="comment"></span>
<a name="l00101"></a>00101 <span class="comment">    /// Function class comparing two value_type pairs.</span>
<a name="l00102"></a><a class="code" href="a00004.html#a87d20557ff74243cab447f15e75e2cc0">00102</a> <span class="comment"></span>    <span class="keyword">typedef</span> <span class="keyword">typename</span> btree_impl::value_compare  <a class="code" href="a00004.html#a87d20557ff74243cab447f15e75e2cc0" title="Function class comparing two value_type pairs.">value_compare</a>;
<a name="l00103"></a>00103 <span class="comment"></span>
<a name="l00104"></a>00104 <span class="comment">    /// Size type used to count keys</span>
<a name="l00105"></a><a class="code" href="a00004.html#a4a2f9618a073d016e89cd8f1628caae1">00105</a> <span class="comment"></span>    <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00001.html#aa692f5303dd2c4fee4958cbbfc3db5da" title="Size type used to count keys.">btree_impl::size_type</a>      <a class="code" href="a00004.html#a4a2f9618a073d016e89cd8f1628caae1" title="Size type used to count keys.">size_type</a>;
<a name="l00106"></a>00106 <span class="comment"></span>
<a name="l00107"></a>00107 <span class="comment">    /// Small structure containing statistics about the tree</span>
<a name="l00108"></a><a class="code" href="a00004.html#a9dd49396431319c3341c4cdcf68385ed">00108</a> <span class="comment"></span>    <span class="keyword">typedef</span> <span class="keyword">typename</span> btree_impl::tree_stats     <a class="code" href="a00004.html#a9dd49396431319c3341c4cdcf68385ed" title="Small structure containing statistics about the tree.">tree_stats</a>;
<a name="l00109"></a>00109 
<a name="l00110"></a>00110 <span class="keyword">public</span>:
<a name="l00111"></a>00111     <span class="comment">// *** Static Constant Options and Values of the B+ Tree</span>
<a name="l00112"></a>00112 <span class="comment"></span>
<a name="l00113"></a>00113 <span class="comment">    /// Base B+ tree parameter: The number of key/data slots in each leaf</span>
<a name="l00114"></a><a class="code" href="a00004.html#a3c005203452c833ae387f7263195631c">00114</a> <span class="comment"></span>    <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span>         <a class="code" href="a00004.html#a3c005203452c833ae387f7263195631c" title="Base B+ tree parameter: The number of key/data slots in each leaf.">leafslotmax</a> =  <a class="code" href="a00001.html#ac6c274f39fce8e14f6a881fc1da39cf8" title="Base B+ tree parameter: The number of key/data slots in each leaf.">btree_impl::leafslotmax</a>;
<a name="l00115"></a>00115 <span class="comment"></span>
<a name="l00116"></a>00116 <span class="comment">    /// Base B+ tree parameter: The number of key slots in each inner node,</span>
<a name="l00117"></a>00117 <span class="comment">    /// this can differ from slots in each leaf.</span>
<a name="l00118"></a><a class="code" href="a00004.html#a0b12dfa41eaa744ad5b9ff6edae4de4b">00118</a> <span class="comment"></span>    <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span>         <a class="code" href="a00004.html#a0b12dfa41eaa744ad5b9ff6edae4de4b" title="Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...">innerslotmax</a> =  <a class="code" href="a00001.html#a78ae296638b9d6961f9101ddf45bf3e0" title="Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...">btree_impl::innerslotmax</a>;
<a name="l00119"></a>00119 <span class="comment"></span>
<a name="l00120"></a>00120 <span class="comment">    /// Computed B+ tree parameter: The minimum number of key/data slots used</span>
<a name="l00121"></a>00121 <span class="comment">    /// in a leaf. If fewer slots are used, the leaf will be merged or slots</span>
<a name="l00122"></a>00122 <span class="comment">    /// shifted from it&#39;s siblings.</span>
<a name="l00123"></a><a class="code" href="a00004.html#a037f1c67f0a692c34b4408657a708221">00123</a> <span class="comment"></span>    <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span>         <a class="code" href="a00004.html#a037f1c67f0a692c34b4408657a708221" title="Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.">minleafslots</a> = <a class="code" href="a00001.html#ad8525611bf3b079ca4ab13dbab9b23c0" title="Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.">btree_impl::minleafslots</a>;
<a name="l00124"></a>00124 <span class="comment"></span>
<a name="l00125"></a>00125 <span class="comment">    /// Computed B+ tree parameter: The minimum number of key slots used</span>
<a name="l00126"></a>00126 <span class="comment">    /// in an inner node. If fewer slots are used, the inner node will be</span>
<a name="l00127"></a>00127 <span class="comment">    /// merged or slots shifted from it&#39;s siblings.</span>
<a name="l00128"></a><a class="code" href="a00004.html#a156a4561d7fe12679b22e3d618a69416">00128</a> <span class="comment"></span>    <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span>         <a class="code" href="a00004.html#a156a4561d7fe12679b22e3d618a69416" title="Computed B+ tree parameter: The minimum number of key slots used in an inner node.">mininnerslots</a> = <a class="code" href="a00001.html#aefbcc95b60d5bae8dd7ba9c25e5b6654" title="Computed B+ tree parameter: The minimum number of key slots used in an inner node.">btree_impl::mininnerslots</a>;
<a name="l00129"></a>00129 <span class="comment"></span>
<a name="l00130"></a>00130 <span class="comment">    /// Debug parameter: Enables expensive and thorough checking of the B+ tree</span>
<a name="l00131"></a>00131 <span class="comment">    /// invariants after each insert/erase operation.</span>
<a name="l00132"></a><a class="code" href="a00004.html#a18eec4e7f698019480bb8d96b1ceabd4">00132</a> <span class="comment"></span>    <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">bool</span>                   <a class="code" href="a00004.html#a18eec4e7f698019480bb8d96b1ceabd4" title="Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...">selfverify</a> = <a class="code" href="a00001.html#a598601fa16cfb97b8b60a4eae6bde5ae" title="Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...">btree_impl::selfverify</a>;
<a name="l00133"></a>00133 <span class="comment"></span>
<a name="l00134"></a>00134 <span class="comment">    /// Debug parameter: Prints out lots of debug information about how the</span>
<a name="l00135"></a>00135 <span class="comment">    /// algorithms change the tree. Requires the header file to be compiled</span>
<a name="l00136"></a>00136 <span class="comment">    /// with BTREE_DEBUG and the key type must be std::ostream printable.</span>
<a name="l00137"></a><a class="code" href="a00004.html#aa9abe4fe3ec8c3ff40392c9a4fd3d587">00137</a> <span class="comment"></span>    <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">bool</span>                   <a class="code" href="a00004.html#aa9abe4fe3ec8c3ff40392c9a4fd3d587" title="Debug parameter: Prints out lots of debug information about how the algorithms change the tree...">debug</a> = <a class="code" href="a00001.html#a224f31a88d50490e14f0f291d70ef2fc" title="Debug parameter: Prints out lots of debug information about how the algorithms change the tree...">btree_impl::debug</a>;
<a name="l00138"></a>00138 <span class="comment"></span>
<a name="l00139"></a>00139 <span class="comment">    /// Operational parameter: Allow duplicate keys in the btree.</span>
<a name="l00140"></a><a class="code" href="a00004.html#a7a93d908ea2b967d4a54946a37675e25">00140</a> <span class="comment"></span>    <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">bool</span>                   <a class="code" href="a00004.html#a7a93d908ea2b967d4a54946a37675e25" title="Operational parameter: Allow duplicate keys in the btree.">allow_duplicates</a> = <a class="code" href="a00001.html#acd41575a35d1c5d55e955aafc9762454" title="Sixth template parameter: Allow duplicate keys in the B+ tree.">btree_impl::allow_duplicates</a>;
<a name="l00141"></a>00141 
<a name="l00142"></a>00142 <span class="keyword">public</span>:
<a name="l00143"></a>00143     <span class="comment">// *** Iterators and Reverse Iterators</span>
<a name="l00144"></a>00144 <span class="comment"></span>
<a name="l00145"></a>00145 <span class="comment">    /// STL-like iterator object for B+ tree items. The iterator points to a</span>
<a name="l00146"></a>00146 <span class="comment">    /// specific slot number in a leaf.</span>
<a name="l00147"></a><a class="code" href="a00004.html#a2568bb45a7daa093f6e0c1869c693597">00147</a> <span class="comment"></span>    <span class="keyword">typedef</span> <span class="keyword">typename</span> btree_impl::iterator               <a class="code" href="a00004.html#a2568bb45a7daa093f6e0c1869c693597" title="STL-like iterator object for B+ tree items.">iterator</a>;
<a name="l00148"></a>00148 <span class="comment"></span>
<a name="l00149"></a>00149 <span class="comment">    /// STL-like iterator object for B+ tree items. The iterator points to a</span>
<a name="l00150"></a>00150 <span class="comment">    /// specific slot number in a leaf.</span>
<a name="l00151"></a><a class="code" href="a00004.html#a267163dd98f108686cf17f2604d2bf81">00151</a> <span class="comment"></span>    <span class="keyword">typedef</span> <span class="keyword">typename</span> btree_impl::const_iterator         <a class="code" href="a00004.html#a267163dd98f108686cf17f2604d2bf81" title="STL-like iterator object for B+ tree items.">const_iterator</a>;
<a name="l00152"></a>00152 <span class="comment"></span>
<a name="l00153"></a>00153 <span class="comment">    /// create mutable reverse iterator by using STL magic</span>
<a name="l00154"></a><a class="code" href="a00004.html#a204cd4ff4807b9c35605b1ccc3cb597a">00154</a> <span class="comment"></span>    <span class="keyword">typedef</span> <span class="keyword">typename</span> btree_impl::reverse_iterator       <a class="code" href="a00004.html#a204cd4ff4807b9c35605b1ccc3cb597a" title="create mutable reverse iterator by using STL magic">reverse_iterator</a>;
<a name="l00155"></a>00155 <span class="comment"></span>
<a name="l00156"></a>00156 <span class="comment">    /// create constant reverse iterator by using STL magic</span>
<a name="l00157"></a><a class="code" href="a00004.html#a581abfef3fb0eab26b2833165f7314b7">00157</a> <span class="comment"></span>    <span class="keyword">typedef</span> <span class="keyword">typename</span> btree_impl::const_reverse_iterator <a class="code" href="a00004.html#a581abfef3fb0eab26b2833165f7314b7" title="create constant reverse iterator by using STL magic">const_reverse_iterator</a>;
<a name="l00158"></a>00158 
<a name="l00159"></a>00159 <span class="keyword">private</span>:
<a name="l00160"></a>00160     <span class="comment">// *** Tree Implementation Object</span>
<a name="l00161"></a>00161 <span class="comment"></span>
<a name="l00162"></a>00162 <span class="comment">    /// The contained implementation object</span>
<a name="l00163"></a><a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69">00163</a> <span class="comment"></span>    <a class="code" href="a00001.html">btree_impl</a>  <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>;
<a name="l00164"></a>00164 
<a name="l00165"></a>00165 <span class="keyword">public</span>:
<a name="l00166"></a>00166     <span class="comment">// *** Constructors and Destructor</span>
<a name="l00167"></a>00167 <span class="comment"></span>
<a name="l00168"></a>00168 <span class="comment">    /// Default constructor initializing an empty B+ tree with the standard key</span>
<a name="l00169"></a>00169 <span class="comment">    /// comparison function</span>
<a name="l00170"></a><a class="code" href="a00004.html#aa00c6e1abb83866bb9c96098808677c9">00170</a> <span class="comment"></span>    <span class="keyword">explicit</span> <span class="keyword">inline</span> <a class="code" href="a00004.html#aa00c6e1abb83866bb9c96098808677c9" title="Default constructor initializing an empty B+ tree with the standard key comparison function...">btree_map</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#a5d0f64823a786b0652038b8702ae5343" title="Fifth template parameter: STL allocator.">allocator_type</a> &amp;alloc = <a class="code" href="a00004.html#a5d0f64823a786b0652038b8702ae5343" title="Fifth template parameter: STL allocator.">allocator_type</a>())
<a name="l00171"></a>00171         : <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>(alloc)
<a name="l00172"></a>00172     {
<a name="l00173"></a>00173     }
<a name="l00174"></a>00174 <span class="comment"></span>
<a name="l00175"></a>00175 <span class="comment">    /// Constructor initializing an empty B+ tree with a special key</span>
<a name="l00176"></a>00176 <span class="comment">    /// comparison object</span>
<a name="l00177"></a><a class="code" href="a00004.html#a75fc3cca006f9f80e26738761f5f012b">00177</a> <span class="comment"></span>    <span class="keyword">explicit</span> <span class="keyword">inline</span> <a class="code" href="a00004.html#aa00c6e1abb83866bb9c96098808677c9" title="Default constructor initializing an empty B+ tree with the standard key comparison function...">btree_map</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#a7c428c8ee8f8ec5041739f6bb55089c1" title="Third template parameter: Key comparison function object.">key_compare</a> &amp;kcf,
<a name="l00178"></a>00178                               <span class="keyword">const</span> <a class="code" href="a00004.html#a5d0f64823a786b0652038b8702ae5343" title="Fifth template parameter: STL allocator.">allocator_type</a> &amp;alloc = <a class="code" href="a00004.html#a5d0f64823a786b0652038b8702ae5343" title="Fifth template parameter: STL allocator.">allocator_type</a>())
<a name="l00179"></a>00179         : <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>(kcf, alloc)
<a name="l00180"></a>00180     {
<a name="l00181"></a>00181     }
<a name="l00182"></a>00182 <span class="comment"></span>
<a name="l00183"></a>00183 <span class="comment">    /// Constructor initializing a B+ tree with the range [first,last)</span>
<a name="l00184"></a>00184 <span class="comment"></span>    <span class="keyword">template</span> &lt;<span class="keyword">class</span> InputIterator&gt;
<a name="l00185"></a><a class="code" href="a00004.html#a1801d9d4587edf16df5dd97fca4e9d3f">00185</a>     <span class="keyword">inline</span> <a class="code" href="a00004.html#aa00c6e1abb83866bb9c96098808677c9" title="Default constructor initializing an empty B+ tree with the standard key comparison function...">btree_map</a>(InputIterator first, InputIterator last,
<a name="l00186"></a>00186                      <span class="keyword">const</span> <a class="code" href="a00004.html#a5d0f64823a786b0652038b8702ae5343" title="Fifth template parameter: STL allocator.">allocator_type</a> &amp;alloc = <a class="code" href="a00004.html#a5d0f64823a786b0652038b8702ae5343" title="Fifth template parameter: STL allocator.">allocator_type</a>())
<a name="l00187"></a>00187         : <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>(first, last, alloc)
<a name="l00188"></a>00188     {
<a name="l00189"></a>00189     }
<a name="l00190"></a>00190 <span class="comment"></span>
<a name="l00191"></a>00191 <span class="comment">    /// Constructor initializing a B+ tree with the range [first,last) and a</span>
<a name="l00192"></a>00192 <span class="comment">    /// special key comparison object</span>
<a name="l00193"></a>00193 <span class="comment"></span>    <span class="keyword">template</span> &lt;<span class="keyword">class</span> InputIterator&gt;
<a name="l00194"></a><a class="code" href="a00004.html#a92d53ace52f64ef0488a3df434bc2483">00194</a>     <span class="keyword">inline</span> <a class="code" href="a00004.html#aa00c6e1abb83866bb9c96098808677c9" title="Default constructor initializing an empty B+ tree with the standard key comparison function...">btree_map</a>(InputIterator first, InputIterator last, <span class="keyword">const</span> <a class="code" href="a00004.html#a7c428c8ee8f8ec5041739f6bb55089c1" title="Third template parameter: Key comparison function object.">key_compare</a> &amp;kcf,
<a name="l00195"></a>00195                      <span class="keyword">const</span> <a class="code" href="a00004.html#a5d0f64823a786b0652038b8702ae5343" title="Fifth template parameter: STL allocator.">allocator_type</a> &amp;alloc = <a class="code" href="a00004.html#a5d0f64823a786b0652038b8702ae5343" title="Fifth template parameter: STL allocator.">allocator_type</a>())
<a name="l00196"></a>00196         : <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>(first, last, kcf, alloc)
<a name="l00197"></a>00197     {
<a name="l00198"></a>00198     }
<a name="l00199"></a>00199 <span class="comment"></span>
<a name="l00200"></a>00200 <span class="comment">    /// Frees up all used B+ tree memory pages</span>
<a name="l00201"></a><a class="code" href="a00004.html#acd6d30ce67dc6d665b29cafc8fdb7221">00201</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#acd6d30ce67dc6d665b29cafc8fdb7221" title="Frees up all used B+ tree memory pages.">~btree_map</a>()
<a name="l00202"></a>00202     {
<a name="l00203"></a>00203     }
<a name="l00204"></a>00204 <span class="comment"></span>
<a name="l00205"></a>00205 <span class="comment">    /// Fast swapping of two identical B+ tree objects.</span>
<a name="l00206"></a><a class="code" href="a00004.html#a5569e8d5495de8db8cd8c51b5797c9b0">00206</a> <span class="comment"></span>    <span class="keywordtype">void</span> <a class="code" href="a00004.html#a5569e8d5495de8db8cd8c51b5797c9b0" title="Fast swapping of two identical B+ tree objects.">swap</a>(<span class="keyword">self</span>&amp; from)
<a name="l00207"></a>00207     {
<a name="l00208"></a>00208         <a class="code" href="a00004.html#a5569e8d5495de8db8cd8c51b5797c9b0" title="Fast swapping of two identical B+ tree objects.">std::swap</a>(<a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>, from.tree);
<a name="l00209"></a>00209     }
<a name="l00210"></a>00210 
<a name="l00211"></a>00211 <span class="keyword">public</span>:
<a name="l00212"></a>00212     <span class="comment">// *** Key and Value Comparison Function Objects</span>
<a name="l00213"></a>00213 <span class="comment"></span>
<a name="l00214"></a>00214 <span class="comment">    /// Constant access to the key comparison object sorting the B+ tree</span>
<a name="l00215"></a><a class="code" href="a00004.html#abab498d7a1a6806b11e9be08558451ec">00215</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#a7c428c8ee8f8ec5041739f6bb55089c1" title="Third template parameter: Key comparison function object.">key_compare</a> <a class="code" href="a00004.html#abab498d7a1a6806b11e9be08558451ec" title="Constant access to the key comparison object sorting the B+ tree.">key_comp</a>()<span class="keyword"> const</span>
<a name="l00216"></a>00216 <span class="keyword">    </span>{
<a name="l00217"></a>00217         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a6200a8a00989f77f053e1200da7f816b" title="Constant access to the key comparison object sorting the B+ tree.">key_comp</a>();
<a name="l00218"></a>00218     }
<a name="l00219"></a>00219 <span class="comment"></span>
<a name="l00220"></a>00220 <span class="comment">    /// Constant access to a constructed value_type comparison object. required</span>
<a name="l00221"></a>00221 <span class="comment">    /// by the STL</span>
<a name="l00222"></a><a class="code" href="a00004.html#ae4426f6512a95d1cb6e7cb61e23b7248">00222</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#a87d20557ff74243cab447f15e75e2cc0" title="Function class comparing two value_type pairs.">value_compare</a> <a class="code" href="a00004.html#ae4426f6512a95d1cb6e7cb61e23b7248" title="Constant access to a constructed value_type comparison object.">value_comp</a>()<span class="keyword"> const</span>
<a name="l00223"></a>00223 <span class="keyword">    </span>{
<a name="l00224"></a>00224         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a35152f783bc65c97504cd22d1812f673" title="Constant access to a constructed value_type comparison object.">value_comp</a>();
<a name="l00225"></a>00225     }
<a name="l00226"></a>00226 
<a name="l00227"></a>00227 <span class="keyword">public</span>:
<a name="l00228"></a>00228     <span class="comment">// *** Allocators</span>
<a name="l00229"></a>00229 <span class="comment"></span>
<a name="l00230"></a>00230 <span class="comment">    /// Return the base node allocator provided during construction.</span>
<a name="l00231"></a><a class="code" href="a00004.html#a76fe9e37d2d5c102cc2939a512d441eb">00231</a> <span class="comment"></span>    <a class="code" href="a00004.html#a5d0f64823a786b0652038b8702ae5343" title="Fifth template parameter: STL allocator.">allocator_type</a> <a class="code" href="a00004.html#a76fe9e37d2d5c102cc2939a512d441eb" title="Return the base node allocator provided during construction.">get_allocator</a>()<span class="keyword"> const</span>
<a name="l00232"></a>00232 <span class="keyword">    </span>{
<a name="l00233"></a>00233         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#ad7b097e1a4301e319d8a7e6f6bb661fd" title="Return the base node allocator provided during construction.">get_allocator</a>();
<a name="l00234"></a>00234     }
<a name="l00235"></a>00235 
<a name="l00236"></a>00236 <span class="keyword">public</span>:
<a name="l00237"></a>00237     <span class="comment">// *** Fast Destruction of the B+ Tree</span>
<a name="l00238"></a>00238 <span class="comment"></span>
<a name="l00239"></a>00239 <span class="comment">    /// Frees all key/data pairs and all nodes of the tree</span>
<a name="l00240"></a><a class="code" href="a00004.html#ad2795fc102f76c2a130681fa579c3310">00240</a> <span class="comment"></span>    <span class="keywordtype">void</span> <a class="code" href="a00004.html#ad2795fc102f76c2a130681fa579c3310" title="Frees all key/data pairs and all nodes of the tree.">clear</a>()
<a name="l00241"></a>00241     {
<a name="l00242"></a>00242         <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#aa2acf975007740100b9803fcea573036" title="Frees all key/data pairs and all nodes of the tree.">clear</a>();
<a name="l00243"></a>00243     }
<a name="l00244"></a>00244 
<a name="l00245"></a>00245 <span class="keyword">public</span>:
<a name="l00246"></a>00246     <span class="comment">// *** STL Iterator Construction Functions</span>
<a name="l00247"></a>00247 <span class="comment"></span>
<a name="l00248"></a>00248 <span class="comment">    /// Constructs a read/data-write iterator that points to the first slot in</span>
<a name="l00249"></a>00249 <span class="comment">    /// the first leaf of the B+ tree.</span>
<a name="l00250"></a><a class="code" href="a00004.html#a34d4041f1b3e65a89e73ce9f527b0f41">00250</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#a2568bb45a7daa093f6e0c1869c693597" title="STL-like iterator object for B+ tree items.">iterator</a> <a class="code" href="a00004.html#a34d4041f1b3e65a89e73ce9f527b0f41" title="Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree...">begin</a>()
<a name="l00251"></a>00251     {
<a name="l00252"></a>00252         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a564a6ea78bcc0de0bbc1fdff65f547fd" title="Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree...">begin</a>();
<a name="l00253"></a>00253     }
<a name="l00254"></a>00254 <span class="comment"></span>
<a name="l00255"></a>00255 <span class="comment">    /// Constructs a read/data-write iterator that points to the first invalid</span>
<a name="l00256"></a>00256 <span class="comment">    /// slot in the last leaf of the B+ tree.</span>
<a name="l00257"></a><a class="code" href="a00004.html#ab5c57d291943ba0ca01e5858027e74a0">00257</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#a2568bb45a7daa093f6e0c1869c693597" title="STL-like iterator object for B+ tree items.">iterator</a> <a class="code" href="a00004.html#ab5c57d291943ba0ca01e5858027e74a0" title="Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...">end</a>()
<a name="l00258"></a>00258     {
<a name="l00259"></a>00259         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a8f1fbaf7eabefca66188e2bf6996573d" title="Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...">end</a>();
<a name="l00260"></a>00260     }
<a name="l00261"></a>00261 <span class="comment"></span>
<a name="l00262"></a>00262 <span class="comment">    /// Constructs a read-only constant iterator that points to the first slot</span>
<a name="l00263"></a>00263 <span class="comment">    /// in the first leaf of the B+ tree.</span>
<a name="l00264"></a><a class="code" href="a00004.html#ad25d2a48e92182db08213676181470c0">00264</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#a267163dd98f108686cf17f2604d2bf81" title="STL-like iterator object for B+ tree items.">const_iterator</a> <a class="code" href="a00004.html#a34d4041f1b3e65a89e73ce9f527b0f41" title="Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree...">begin</a>()<span class="keyword"> const</span>
<a name="l00265"></a>00265 <span class="keyword">    </span>{
<a name="l00266"></a>00266         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a564a6ea78bcc0de0bbc1fdff65f547fd" title="Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree...">begin</a>();
<a name="l00267"></a>00267     }
<a name="l00268"></a>00268 <span class="comment"></span>
<a name="l00269"></a>00269 <span class="comment">    /// Constructs a read-only constant iterator that points to the first</span>
<a name="l00270"></a>00270 <span class="comment">    /// invalid slot in the last leaf of the B+ tree.</span>
<a name="l00271"></a><a class="code" href="a00004.html#ab0f8eb359766094f2e8d5128e4daf704">00271</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#a267163dd98f108686cf17f2604d2bf81" title="STL-like iterator object for B+ tree items.">const_iterator</a> <a class="code" href="a00004.html#ab5c57d291943ba0ca01e5858027e74a0" title="Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...">end</a>()<span class="keyword"> const</span>
<a name="l00272"></a>00272 <span class="keyword">    </span>{
<a name="l00273"></a>00273         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a8f1fbaf7eabefca66188e2bf6996573d" title="Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...">end</a>();
<a name="l00274"></a>00274     }
<a name="l00275"></a>00275 <span class="comment"></span>
<a name="l00276"></a>00276 <span class="comment">    /// Constructs a read/data-write reverse iterator that points to the first</span>
<a name="l00277"></a>00277 <span class="comment">    /// invalid slot in the last leaf of the B+ tree. Uses STL magic.</span>
<a name="l00278"></a><a class="code" href="a00004.html#a7163405774d2a2bada3166d94c6fe5d3">00278</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#a204cd4ff4807b9c35605b1ccc3cb597a" title="create mutable reverse iterator by using STL magic">reverse_iterator</a> <a class="code" href="a00004.html#a7163405774d2a2bada3166d94c6fe5d3" title="Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...">rbegin</a>()
<a name="l00279"></a>00279     {
<a name="l00280"></a>00280         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a4e2f4ba4141820f4bc5782298c261aa5" title="Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...">rbegin</a>();
<a name="l00281"></a>00281     }
<a name="l00282"></a>00282 <span class="comment"></span>
<a name="l00283"></a>00283 <span class="comment">    /// Constructs a read/data-write reverse iterator that points to the first</span>
<a name="l00284"></a>00284 <span class="comment">    /// slot in the first leaf of the B+ tree. Uses STL magic.</span>
<a name="l00285"></a><a class="code" href="a00004.html#a07e9e77ecd8cd828d32bca22a9f45c2a">00285</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#a204cd4ff4807b9c35605b1ccc3cb597a" title="create mutable reverse iterator by using STL magic">reverse_iterator</a> <a class="code" href="a00004.html#a07e9e77ecd8cd828d32bca22a9f45c2a" title="Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...">rend</a>()
<a name="l00286"></a>00286     {
<a name="l00287"></a>00287         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a625d6f5e37cfed631a403fe36fa818dc" title="Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...">rend</a>();
<a name="l00288"></a>00288     }
<a name="l00289"></a>00289 <span class="comment"></span>
<a name="l00290"></a>00290 <span class="comment">    /// Constructs a read-only reverse iterator that points to the first</span>
<a name="l00291"></a>00291 <span class="comment">    /// invalid slot in the last leaf of the B+ tree. Uses STL magic.</span>
<a name="l00292"></a><a class="code" href="a00004.html#a0c8ee35fbd098077983ac3b74a20cdd2">00292</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#a581abfef3fb0eab26b2833165f7314b7" title="create constant reverse iterator by using STL magic">const_reverse_iterator</a> <a class="code" href="a00004.html#a7163405774d2a2bada3166d94c6fe5d3" title="Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...">rbegin</a>()<span class="keyword"> const</span>
<a name="l00293"></a>00293 <span class="keyword">    </span>{
<a name="l00294"></a>00294         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a4e2f4ba4141820f4bc5782298c261aa5" title="Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...">rbegin</a>();
<a name="l00295"></a>00295     }
<a name="l00296"></a>00296 <span class="comment"></span>
<a name="l00297"></a>00297 <span class="comment">    /// Constructs a read-only reverse iterator that points to the first slot</span>
<a name="l00298"></a>00298 <span class="comment">    /// in the first leaf of the B+ tree. Uses STL magic.</span>
<a name="l00299"></a><a class="code" href="a00004.html#a3745c3bc3523e3671269a5f6bf9fd2de">00299</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#a581abfef3fb0eab26b2833165f7314b7" title="create constant reverse iterator by using STL magic">const_reverse_iterator</a> <a class="code" href="a00004.html#a07e9e77ecd8cd828d32bca22a9f45c2a" title="Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...">rend</a>()<span class="keyword"> const</span>
<a name="l00300"></a>00300 <span class="keyword">    </span>{
<a name="l00301"></a>00301         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a625d6f5e37cfed631a403fe36fa818dc" title="Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...">rend</a>();
<a name="l00302"></a>00302     }
<a name="l00303"></a>00303 
<a name="l00304"></a>00304 <span class="keyword">public</span>:
<a name="l00305"></a>00305     <span class="comment">// *** Access Functions to the Item Count</span>
<a name="l00306"></a>00306 <span class="comment"></span>
<a name="l00307"></a>00307 <span class="comment">    /// Return the number of key/data pairs in the B+ tree</span>
<a name="l00308"></a><a class="code" href="a00004.html#a4816cbf72826412000ffebf49eae033a">00308</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#a4a2f9618a073d016e89cd8f1628caae1" title="Size type used to count keys.">size_type</a> <a class="code" href="a00004.html#a4816cbf72826412000ffebf49eae033a" title="Return the number of key/data pairs in the B+ tree.">size</a>()<span class="keyword"> const</span>
<a name="l00309"></a>00309 <span class="keyword">    </span>{
<a name="l00310"></a>00310         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a3942d7144bc93cf094b62f03e6113f4e" title="Return the number of key/data pairs in the B+ tree.">size</a>();
<a name="l00311"></a>00311     }
<a name="l00312"></a>00312 <span class="comment"></span>
<a name="l00313"></a>00313 <span class="comment">    /// Returns true if there is at least one key/data pair in the B+ tree</span>
<a name="l00314"></a><a class="code" href="a00004.html#aeae6000acb62e6b13563efe1d1fa1660">00314</a> <span class="comment"></span>    <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00004.html#aeae6000acb62e6b13563efe1d1fa1660" title="Returns true if there is at least one key/data pair in the B+ tree.">empty</a>()<span class="keyword"> const</span>
<a name="l00315"></a>00315 <span class="keyword">    </span>{
<a name="l00316"></a>00316         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#ad7cf0c4833d2ea3fcd79df4c884bab40" title="Returns true if there is at least one key/data pair in the B+ tree.">empty</a>();
<a name="l00317"></a>00317     }
<a name="l00318"></a>00318 <span class="comment"></span>
<a name="l00319"></a>00319 <span class="comment">    /// Returns the largest possible size of the B+ Tree. This is just a</span>
<a name="l00320"></a>00320 <span class="comment">    /// function required by the STL standard, the B+ Tree can hold more items.</span>
<a name="l00321"></a><a class="code" href="a00004.html#ae0655211e7a2c51312cfaf7b4cd87836">00321</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#a4a2f9618a073d016e89cd8f1628caae1" title="Size type used to count keys.">size_type</a> <a class="code" href="a00004.html#ae0655211e7a2c51312cfaf7b4cd87836" title="Returns the largest possible size of the B+ Tree.">max_size</a>()<span class="keyword"> const</span>
<a name="l00322"></a>00322 <span class="keyword">    </span>{
<a name="l00323"></a>00323         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a3285e41cd6c4566e99d8c82803ad4d92" title="Returns the largest possible size of the B+ Tree.">max_size</a>();
<a name="l00324"></a>00324     }
<a name="l00325"></a>00325 <span class="comment"></span>
<a name="l00326"></a>00326 <span class="comment">    /// Return a const reference to the current statistics.</span>
<a name="l00327"></a><a class="code" href="a00004.html#aa5374a517934ddbb6bae7053eeaacad3">00327</a> <span class="comment"></span>    <span class="keyword">inline</span> <span class="keyword">const</span> <a class="code" href="a00004.html#a9dd49396431319c3341c4cdcf68385ed" title="Small structure containing statistics about the tree.">tree_stats</a>&amp; <a class="code" href="a00004.html#aa5374a517934ddbb6bae7053eeaacad3" title="Return a const reference to the current statistics.">get_stats</a>()<span class="keyword"> const</span>
<a name="l00328"></a>00328 <span class="keyword">    </span>{
<a name="l00329"></a>00329         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a81c7f4e56b3421976855daf40c6e20fc" title="Return a const reference to the current statistics.">get_stats</a>();
<a name="l00330"></a>00330     }
<a name="l00331"></a>00331 
<a name="l00332"></a>00332 <span class="keyword">public</span>:
<a name="l00333"></a>00333     <span class="comment">// *** Standard Access Functions Querying the Tree by Descending to a Leaf</span>
<a name="l00334"></a>00334 <span class="comment"></span>
<a name="l00335"></a>00335 <span class="comment">    /// Non-STL function checking whether a key is in the B+ tree. The same as</span>
<a name="l00336"></a>00336 <span class="comment">    /// (find(k) != end()) or (count() != 0).</span>
<a name="l00337"></a><a class="code" href="a00004.html#a0aa2e7bf016864cb2bfe689a5967abf6">00337</a> <span class="comment"></span>    <span class="keywordtype">bool</span> <a class="code" href="a00004.html#a0aa2e7bf016864cb2bfe689a5967abf6" title="Non-STL function checking whether a key is in the B+ tree.">exists</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a> &amp;key)<span class="keyword"> const</span>
<a name="l00338"></a>00338 <span class="keyword">    </span>{
<a name="l00339"></a>00339         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a3c1b922d80faa7d5864237b4791a7961" title="Non-STL function checking whether a key is in the B+ tree.">exists</a>(key);
<a name="l00340"></a>00340     }
<a name="l00341"></a>00341 <span class="comment"></span>
<a name="l00342"></a>00342 <span class="comment">    /// Tries to locate a key in the B+ tree and returns an iterator to the</span>
<a name="l00343"></a>00343 <span class="comment">    /// key/data slot if found. If unsuccessful it returns end().</span>
<a name="l00344"></a><a class="code" href="a00004.html#a8db4682cc1dc34e2dd95d6ded2e2af65">00344</a> <span class="comment"></span>    <a class="code" href="a00004.html#a2568bb45a7daa093f6e0c1869c693597" title="STL-like iterator object for B+ tree items.">iterator</a> <a class="code" href="a00004.html#a8db4682cc1dc34e2dd95d6ded2e2af65" title="Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found...">find</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a> &amp;key)
<a name="l00345"></a>00345     {
<a name="l00346"></a>00346         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a90bd85f703bb74d7ab7dc967bf8d712f" title="Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found...">find</a>(key);
<a name="l00347"></a>00347     }
<a name="l00348"></a>00348 <span class="comment"></span>
<a name="l00349"></a>00349 <span class="comment">    /// Tries to locate a key in the B+ tree and returns an constant iterator</span>
<a name="l00350"></a>00350 <span class="comment">    /// to the key/data slot if found. If unsuccessful it returns end().</span>
<a name="l00351"></a><a class="code" href="a00004.html#a9c5ac09e4fbd11e6b1c106c5d1340281">00351</a> <span class="comment"></span>    <a class="code" href="a00004.html#a267163dd98f108686cf17f2604d2bf81" title="STL-like iterator object for B+ tree items.">const_iterator</a> <a class="code" href="a00004.html#a8db4682cc1dc34e2dd95d6ded2e2af65" title="Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found...">find</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a> &amp;key)<span class="keyword"> const</span>
<a name="l00352"></a>00352 <span class="keyword">    </span>{
<a name="l00353"></a>00353         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a90bd85f703bb74d7ab7dc967bf8d712f" title="Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found...">find</a>(key);
<a name="l00354"></a>00354     }
<a name="l00355"></a>00355 <span class="comment"></span>
<a name="l00356"></a>00356 <span class="comment">    /// Tries to locate a key in the B+ tree and returns the number of</span>
<a name="l00357"></a>00357 <span class="comment">    /// identical key entries found. Since this is a unique map, count()</span>
<a name="l00358"></a>00358 <span class="comment">    /// returns either 0 or 1.</span>
<a name="l00359"></a><a class="code" href="a00004.html#a96abb2181dae3af81233717c33bcb0e1">00359</a> <span class="comment"></span>    <a class="code" href="a00004.html#a4a2f9618a073d016e89cd8f1628caae1" title="Size type used to count keys.">size_type</a> <a class="code" href="a00004.html#a96abb2181dae3af81233717c33bcb0e1" title="Tries to locate a key in the B+ tree and returns the number of identical key entries found...">count</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a> &amp;key)<span class="keyword"> const</span>
<a name="l00360"></a>00360 <span class="keyword">    </span>{
<a name="l00361"></a>00361         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a3882a2b0e2ea8eb43b4261e7f3eb32f2" title="Tries to locate a key in the B+ tree and returns the number of identical key entries found...">count</a>(key);
<a name="l00362"></a>00362     }
<a name="l00363"></a>00363 <span class="comment"></span>
<a name="l00364"></a>00364 <span class="comment">    /// Searches the B+ tree and returns an iterator to the first pair</span>
<a name="l00365"></a>00365 <span class="comment">    /// equal to or greater than key, or end() if all keys are smaller.</span>
<a name="l00366"></a><a class="code" href="a00004.html#a534cf90439e766792a48ff2ab73ddaf6">00366</a> <span class="comment"></span>    <a class="code" href="a00004.html#a2568bb45a7daa093f6e0c1869c693597" title="STL-like iterator object for B+ tree items.">iterator</a> <a class="code" href="a00004.html#a534cf90439e766792a48ff2ab73ddaf6" title="Searches the B+ tree and returns an iterator to the first pair equal to or greater than key...">lower_bound</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a>&amp; key)
<a name="l00367"></a>00367     {
<a name="l00368"></a>00368         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#aa0b7c53085ef7106f3d430d850b4959e" title="Searches the B+ tree and returns an iterator to the first pair equal to or greater than key...">lower_bound</a>(key);
<a name="l00369"></a>00369     }
<a name="l00370"></a>00370 <span class="comment"></span>
<a name="l00371"></a>00371 <span class="comment">    /// Searches the B+ tree and returns a constant iterator to the</span>
<a name="l00372"></a>00372 <span class="comment">    /// first pair equal to or greater than key, or end() if all keys</span>
<a name="l00373"></a>00373 <span class="comment">    /// are smaller.</span>
<a name="l00374"></a><a class="code" href="a00004.html#acdf38e14fcd031d9f315e2bb4d4feff3">00374</a> <span class="comment"></span>    <a class="code" href="a00004.html#a267163dd98f108686cf17f2604d2bf81" title="STL-like iterator object for B+ tree items.">const_iterator</a> <a class="code" href="a00004.html#a534cf90439e766792a48ff2ab73ddaf6" title="Searches the B+ tree and returns an iterator to the first pair equal to or greater than key...">lower_bound</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a>&amp; key)<span class="keyword"> const</span>
<a name="l00375"></a>00375 <span class="keyword">    </span>{
<a name="l00376"></a>00376         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#aa0b7c53085ef7106f3d430d850b4959e" title="Searches the B+ tree and returns an iterator to the first pair equal to or greater than key...">lower_bound</a>(key);
<a name="l00377"></a>00377     }
<a name="l00378"></a>00378 <span class="comment"></span>
<a name="l00379"></a>00379 <span class="comment">    /// Searches the B+ tree and returns an iterator to the first pair</span>
<a name="l00380"></a>00380 <span class="comment">    /// greater than key, or end() if all keys are smaller or equal.</span>
<a name="l00381"></a><a class="code" href="a00004.html#af9f856c49318bfc313306f19f1eaf017">00381</a> <span class="comment"></span>    <a class="code" href="a00004.html#a2568bb45a7daa093f6e0c1869c693597" title="STL-like iterator object for B+ tree items.">iterator</a> <a class="code" href="a00004.html#af9f856c49318bfc313306f19f1eaf017" title="Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys...">upper_bound</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a>&amp; key)
<a name="l00382"></a>00382     {
<a name="l00383"></a>00383         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a0404bb704466a149ea96613b7c5ef3e2" title="Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys...">upper_bound</a>(key);
<a name="l00384"></a>00384     }
<a name="l00385"></a>00385 <span class="comment"></span>
<a name="l00386"></a>00386 <span class="comment">    /// Searches the B+ tree and returns a constant iterator to the</span>
<a name="l00387"></a>00387 <span class="comment">    /// first pair greater than key, or end() if all keys are smaller</span>
<a name="l00388"></a>00388 <span class="comment">    /// or equal.</span>
<a name="l00389"></a><a class="code" href="a00004.html#abc8bb5938b3b290089e668c1352625d3">00389</a> <span class="comment"></span>    <a class="code" href="a00004.html#a267163dd98f108686cf17f2604d2bf81" title="STL-like iterator object for B+ tree items.">const_iterator</a> <a class="code" href="a00004.html#af9f856c49318bfc313306f19f1eaf017" title="Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys...">upper_bound</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a>&amp; key)<span class="keyword"> const</span>
<a name="l00390"></a>00390 <span class="keyword">    </span>{
<a name="l00391"></a>00391         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a0404bb704466a149ea96613b7c5ef3e2" title="Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys...">upper_bound</a>(key);
<a name="l00392"></a>00392     }
<a name="l00393"></a>00393 <span class="comment"></span>
<a name="l00394"></a>00394 <span class="comment">    /// Searches the B+ tree and returns both lower_bound() and upper_bound().</span>
<a name="l00395"></a><a class="code" href="a00004.html#afd2d85bdaf138d241147f99ea4e02d19">00395</a> <span class="comment"></span>    <span class="keyword">inline</span> std::pair&lt;iterator, iterator&gt; <a class="code" href="a00004.html#afd2d85bdaf138d241147f99ea4e02d19" title="Searches the B+ tree and returns both lower_bound() and upper_bound().">equal_range</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a>&amp; key)
<a name="l00396"></a>00396     {
<a name="l00397"></a>00397         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#ac73cf4621b0650fef2ea3ea1d2fd2f90" title="Searches the B+ tree and returns both lower_bound() and upper_bound().">equal_range</a>(key);
<a name="l00398"></a>00398     }
<a name="l00399"></a>00399 <span class="comment"></span>
<a name="l00400"></a>00400 <span class="comment">    /// Searches the B+ tree and returns both lower_bound() and upper_bound().</span>
<a name="l00401"></a><a class="code" href="a00004.html#aefa6fc135b3f91255e868560461e524d">00401</a> <span class="comment"></span>    <span class="keyword">inline</span> std::pair&lt;const_iterator, const_iterator&gt; <a class="code" href="a00004.html#afd2d85bdaf138d241147f99ea4e02d19" title="Searches the B+ tree and returns both lower_bound() and upper_bound().">equal_range</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a>&amp; key)<span class="keyword"> const</span>
<a name="l00402"></a>00402 <span class="keyword">    </span>{
<a name="l00403"></a>00403         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#ac73cf4621b0650fef2ea3ea1d2fd2f90" title="Searches the B+ tree and returns both lower_bound() and upper_bound().">equal_range</a>(key);
<a name="l00404"></a>00404     }
<a name="l00405"></a>00405 
<a name="l00406"></a>00406 <span class="keyword">public</span>:
<a name="l00407"></a>00407     <span class="comment">// *** B+ Tree Object Comparison Functions</span>
<a name="l00408"></a>00408 <span class="comment"></span>
<a name="l00409"></a>00409 <span class="comment">    /// Equality relation of B+ trees of the same type. B+ trees of the same</span>
<a name="l00410"></a>00410 <span class="comment">    /// size and equal elements (both key and data) are considered</span>
<a name="l00411"></a>00411 <span class="comment">    /// equal.</span>
<a name="l00412"></a><a class="code" href="a00004.html#a2fdda35a2a822e8fe45cda8f5f02dd3f">00412</a> <span class="comment"></span>    <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00004.html#a2fdda35a2a822e8fe45cda8f5f02dd3f" title="Equality relation of B+ trees of the same type.">operator==</a>(<span class="keyword">const</span> <span class="keyword">self</span> &amp;other)<span class="keyword"> const</span>
<a name="l00413"></a>00413 <span class="keyword">    </span>{
<a name="l00414"></a>00414         <span class="keywordflow">return</span> (<a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a> == other.tree);
<a name="l00415"></a>00415     }
<a name="l00416"></a>00416 <span class="comment"></span>
<a name="l00417"></a>00417 <span class="comment">    /// Inequality relation. Based on operator==.</span>
<a name="l00418"></a><a class="code" href="a00004.html#a5246dc846558507311336980cc81ddcb">00418</a> <span class="comment"></span>    <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00004.html#a5246dc846558507311336980cc81ddcb" title="Inequality relation. Based on operator==.">operator!=</a>(<span class="keyword">const</span> <span class="keyword">self</span> &amp;other)<span class="keyword"> const</span>
<a name="l00419"></a>00419 <span class="keyword">    </span>{
<a name="l00420"></a>00420         <span class="keywordflow">return</span> (<a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a> != other.tree);
<a name="l00421"></a>00421     }
<a name="l00422"></a>00422 <span class="comment"></span>
<a name="l00423"></a>00423 <span class="comment">    /// Total ordering relation of B+ trees of the same type. It uses</span>
<a name="l00424"></a>00424 <span class="comment">    /// std::lexicographical_compare() for the actual comparison of elements.</span>
<a name="l00425"></a><a class="code" href="a00004.html#aa9045db3cfebd6e60b0000531a5fdeb6">00425</a> <span class="comment"></span>    <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00004.html#aa9045db3cfebd6e60b0000531a5fdeb6" title="Total ordering relation of B+ trees of the same type.">operator&lt;</a>(<span class="keyword">const</span> <span class="keyword">self</span> &amp;other)<span class="keyword"> const</span>
<a name="l00426"></a>00426 <span class="keyword">    </span>{
<a name="l00427"></a>00427         <span class="keywordflow">return</span> (<a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a> &lt; other.tree);
<a name="l00428"></a>00428     }
<a name="l00429"></a>00429 <span class="comment"></span>
<a name="l00430"></a>00430 <span class="comment">    /// Greater relation. Based on operator&lt;.</span>
<a name="l00431"></a><a class="code" href="a00004.html#a4b4a740ce7e953d1010fcbb6634a0df8">00431</a> <span class="comment"></span>    <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00004.html#a4b4a740ce7e953d1010fcbb6634a0df8" title="Greater relation. Based on operator&lt;.">operator&gt;</a>(<span class="keyword">const</span> <span class="keyword">self</span> &amp;other)<span class="keyword"> const</span>
<a name="l00432"></a>00432 <span class="keyword">    </span>{
<a name="l00433"></a>00433         <span class="keywordflow">return</span> (<a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a> &gt; other.tree);
<a name="l00434"></a>00434     }
<a name="l00435"></a>00435 <span class="comment"></span>
<a name="l00436"></a>00436 <span class="comment">    /// Less-equal relation. Based on operator&lt;.</span>
<a name="l00437"></a><a class="code" href="a00004.html#a34082a4270e0f5de6a6c3ba06bd3476a">00437</a> <span class="comment"></span>    <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00004.html#a34082a4270e0f5de6a6c3ba06bd3476a" title="Less-equal relation. Based on operator&lt;.">operator&lt;=</a>(<span class="keyword">const</span> <span class="keyword">self</span> &amp;other)<span class="keyword"> const</span>
<a name="l00438"></a>00438 <span class="keyword">    </span>{
<a name="l00439"></a>00439         <span class="keywordflow">return</span> (<a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a> &lt;= other.tree);
<a name="l00440"></a>00440     }
<a name="l00441"></a>00441 <span class="comment"></span>
<a name="l00442"></a>00442 <span class="comment">    /// Greater-equal relation. Based on operator&lt;.</span>
<a name="l00443"></a><a class="code" href="a00004.html#a04fdaf66979b5191d70d0dfacb601c0b">00443</a> <span class="comment"></span>    <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00004.html#a04fdaf66979b5191d70d0dfacb601c0b" title="Greater-equal relation. Based on operator&lt;.">operator&gt;=</a>(<span class="keyword">const</span> <span class="keyword">self</span> &amp;other)<span class="keyword"> const</span>
<a name="l00444"></a>00444 <span class="keyword">    </span>{
<a name="l00445"></a>00445         <span class="keywordflow">return</span> (<a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a> &gt;= other.tree);
<a name="l00446"></a>00446     }
<a name="l00447"></a>00447 
<a name="l00448"></a>00448 <span class="keyword">public</span>:<span class="comment"></span>
<a name="l00449"></a>00449 <span class="comment">    /// *** Fast Copy: Assign Operator and Copy Constructors</span>
<a name="l00450"></a>00450 <span class="comment"></span><span class="comment"></span>
<a name="l00451"></a>00451 <span class="comment">    /// Assignment operator. All the key/data pairs are copied</span>
<a name="l00452"></a><a class="code" href="a00004.html#a77317e7900903cd29f67b548a8d3ed46">00452</a> <span class="comment"></span>    <span class="keyword">inline</span> <span class="keyword">self</span>&amp; <a class="code" href="a00004.html#a77317e7900903cd29f67b548a8d3ed46" title="*** Fast Copy: Assign Operator and Copy Constructors">operator= </a>(<span class="keyword">const</span> <span class="keyword">self</span> &amp;other)
<a name="l00453"></a>00453     {
<a name="l00454"></a>00454         <span class="keywordflow">if</span> (<span class="keyword">this</span> != &amp;other)
<a name="l00455"></a>00455         {
<a name="l00456"></a>00456             <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a> = other.tree;
<a name="l00457"></a>00457         }
<a name="l00458"></a>00458         <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00459"></a>00459     }
<a name="l00460"></a>00460 <span class="comment"></span>
<a name="l00461"></a>00461 <span class="comment">    /// Copy constructor. The newly initialized B+ tree object will contain a</span>
<a name="l00462"></a>00462 <span class="comment">    /// copy of all key/data pairs.</span>
<a name="l00463"></a><a class="code" href="a00004.html#a27d93017393e732c42e73bb1762815af">00463</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#aa00c6e1abb83866bb9c96098808677c9" title="Default constructor initializing an empty B+ tree with the standard key comparison function...">btree_map</a>(<span class="keyword">const</span> <span class="keyword">self</span> &amp;other)
<a name="l00464"></a>00464         : <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>(other.<a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>)
<a name="l00465"></a>00465     {
<a name="l00466"></a>00466     }
<a name="l00467"></a>00467 
<a name="l00468"></a>00468 <span class="keyword">public</span>:
<a name="l00469"></a>00469     <span class="comment">// *** Public Insertion Functions</span>
<a name="l00470"></a>00470 <span class="comment"></span>
<a name="l00471"></a>00471 <span class="comment">    /// Attempt to insert a key/data pair into the B+ tree. Fails if the pair</span>
<a name="l00472"></a>00472 <span class="comment">    /// is already present.</span>
<a name="l00473"></a><a class="code" href="a00004.html#ac2c8fb3774e84115b1bf403f24afa4b1">00473</a> <span class="comment"></span>    <span class="keyword">inline</span> std::pair&lt;iterator, bool&gt; <a class="code" href="a00004.html#ac2c8fb3774e84115b1bf403f24afa4b1" title="Attempt to insert a key/data pair into the B+ tree.">insert</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#abdb0354081cf05ed114f76b09630001e" title="Construct the STL-required value_type as a composition pair of key and data types.">value_type</a>&amp; x)
<a name="l00474"></a>00474     {
<a name="l00475"></a>00475         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a586dd230f8be24eaeebc75cc95196d78" title="Attempt to insert a key/data pair into the B+ tree.">insert2</a>(x.first, x.second);
<a name="l00476"></a>00476     }
<a name="l00477"></a>00477 <span class="comment"></span>
<a name="l00478"></a>00478 <span class="comment">    /// Attempt to insert a key/data pair into the B+ tree. Beware that if</span>
<a name="l00479"></a>00479 <span class="comment">    /// key_type == data_type, then the template iterator insert() is called</span>
<a name="l00480"></a>00480 <span class="comment">    /// instead. Fails if the inserted pair is already present.</span>
<a name="l00481"></a><a class="code" href="a00004.html#a851a1e09834069a0554ecdff08796d51">00481</a> <span class="comment"></span>    <span class="keyword">inline</span> std::pair&lt;iterator, bool&gt; <a class="code" href="a00004.html#ac2c8fb3774e84115b1bf403f24afa4b1" title="Attempt to insert a key/data pair into the B+ tree.">insert</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a>&amp; key, <span class="keyword">const</span> <a class="code" href="a00004.html#a76d4185d0ff8a2b0fbb572aad2ee93bb" title="Second template parameter: The data type associated with each key.">data_type</a>&amp; data)
<a name="l00482"></a>00482     {
<a name="l00483"></a>00483         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a586dd230f8be24eaeebc75cc95196d78" title="Attempt to insert a key/data pair into the B+ tree.">insert2</a>(key, data);
<a name="l00484"></a>00484     }
<a name="l00485"></a>00485 <span class="comment"></span>
<a name="l00486"></a>00486 <span class="comment">    /// Attempt to insert a key/data pair into the B+ tree. This function is the</span>
<a name="l00487"></a>00487 <span class="comment">    /// same as the other insert, however if key_type == data_type then the</span>
<a name="l00488"></a>00488 <span class="comment">    /// non-template function cannot be called. Fails if the inserted pair is</span>
<a name="l00489"></a>00489 <span class="comment">    /// already present.</span>
<a name="l00490"></a><a class="code" href="a00004.html#a4468eab4a560f8e59130caf052fe2940">00490</a> <span class="comment"></span>    <span class="keyword">inline</span> std::pair&lt;iterator, bool&gt; <a class="code" href="a00004.html#a4468eab4a560f8e59130caf052fe2940" title="Attempt to insert a key/data pair into the B+ tree.">insert2</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a>&amp; key, <span class="keyword">const</span> <a class="code" href="a00004.html#a76d4185d0ff8a2b0fbb572aad2ee93bb" title="Second template parameter: The data type associated with each key.">data_type</a>&amp; data)
<a name="l00491"></a>00491     {
<a name="l00492"></a>00492         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a586dd230f8be24eaeebc75cc95196d78" title="Attempt to insert a key/data pair into the B+ tree.">insert2</a>(key, data);
<a name="l00493"></a>00493     }
<a name="l00494"></a>00494 <span class="comment"></span>
<a name="l00495"></a>00495 <span class="comment">    /// Attempt to insert a key/data pair into the B+ tree. The iterator hint</span>
<a name="l00496"></a>00496 <span class="comment">    /// is currently ignored by the B+ tree insertion routine.</span>
<a name="l00497"></a><a class="code" href="a00004.html#a1c2f94f844ca4193cd4e9dd0f4c89610">00497</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#a2568bb45a7daa093f6e0c1869c693597" title="STL-like iterator object for B+ tree items.">iterator</a> <a class="code" href="a00004.html#ac2c8fb3774e84115b1bf403f24afa4b1" title="Attempt to insert a key/data pair into the B+ tree.">insert</a>(<a class="code" href="a00004.html#a2568bb45a7daa093f6e0c1869c693597" title="STL-like iterator object for B+ tree items.">iterator</a> hint, <span class="keyword">const</span> <a class="code" href="a00004.html#abdb0354081cf05ed114f76b09630001e" title="Construct the STL-required value_type as a composition pair of key and data types.">value_type</a> &amp;x)
<a name="l00498"></a>00498     {
<a name="l00499"></a>00499         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a586dd230f8be24eaeebc75cc95196d78" title="Attempt to insert a key/data pair into the B+ tree.">insert2</a>(hint, x.first, x.second);
<a name="l00500"></a>00500     }
<a name="l00501"></a>00501 <span class="comment"></span>
<a name="l00502"></a>00502 <span class="comment">    /// Attempt to insert a key/data pair into the B+ tree. The iterator hint is</span>
<a name="l00503"></a>00503 <span class="comment">    /// currently ignored by the B+ tree insertion routine.</span>
<a name="l00504"></a><a class="code" href="a00004.html#a68f8b720b175c03ea28d9248dbc7fee5">00504</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#a2568bb45a7daa093f6e0c1869c693597" title="STL-like iterator object for B+ tree items.">iterator</a> <a class="code" href="a00004.html#a4468eab4a560f8e59130caf052fe2940" title="Attempt to insert a key/data pair into the B+ tree.">insert2</a>(<a class="code" href="a00004.html#a2568bb45a7daa093f6e0c1869c693597" title="STL-like iterator object for B+ tree items.">iterator</a> hint, <span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a>&amp; key, <span class="keyword">const</span> <a class="code" href="a00004.html#a76d4185d0ff8a2b0fbb572aad2ee93bb" title="Second template parameter: The data type associated with each key.">data_type</a>&amp; data)
<a name="l00505"></a>00505     {
<a name="l00506"></a>00506         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a586dd230f8be24eaeebc75cc95196d78" title="Attempt to insert a key/data pair into the B+ tree.">insert2</a>(hint, key, data);
<a name="l00507"></a>00507     }
<a name="l00508"></a>00508 <span class="comment"></span>
<a name="l00509"></a>00509 <span class="comment">    /// Returns a reference to the object that is associated with a particular</span>
<a name="l00510"></a>00510 <span class="comment">    /// key. If the map does not already contain such an object, operator[]</span>
<a name="l00511"></a>00511 <span class="comment">    /// inserts the default object data_type().</span>
<a name="l00512"></a><a class="code" href="a00004.html#ab3268177427359a66c11b7f641bb99ae">00512</a> <span class="comment"></span>    <span class="keyword">inline</span> <a class="code" href="a00004.html#a76d4185d0ff8a2b0fbb572aad2ee93bb" title="Second template parameter: The data type associated with each key.">data_type</a>&amp; <a class="code" href="a00004.html#ab3268177427359a66c11b7f641bb99ae" title="Returns a reference to the object that is associated with a particular key.">operator[]</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a>&amp; key)
<a name="l00513"></a>00513     {
<a name="l00514"></a>00514         <a class="code" href="a00004.html#a2568bb45a7daa093f6e0c1869c693597" title="STL-like iterator object for B+ tree items.">iterator</a> i = <a class="code" href="a00004.html#ac2c8fb3774e84115b1bf403f24afa4b1" title="Attempt to insert a key/data pair into the B+ tree.">insert</a>( <a class="code" href="a00004.html#abdb0354081cf05ed114f76b09630001e" title="Construct the STL-required value_type as a composition pair of key and data types.">value_type</a>(key, <a class="code" href="a00004.html#a76d4185d0ff8a2b0fbb572aad2ee93bb" title="Second template parameter: The data type associated with each key.">data_type</a>()) ).first;
<a name="l00515"></a>00515         <span class="keywordflow">return</span> i.data();
<a name="l00516"></a>00516     }
<a name="l00517"></a>00517 <span class="comment"></span>
<a name="l00518"></a>00518 <span class="comment">    /// Attempt to insert the range [first,last) of value_type pairs into the B+</span>
<a name="l00519"></a>00519 <span class="comment">    /// tree. Each key/data pair is inserted individually.</span>
<a name="l00520"></a>00520 <span class="comment"></span>    <span class="keyword">template</span> &lt;<span class="keyword">typename</span> InputIterator&gt;
<a name="l00521"></a><a class="code" href="a00004.html#a783db2843544f7f9f3c3fb498c283d4c">00521</a>     <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="a00004.html#ac2c8fb3774e84115b1bf403f24afa4b1" title="Attempt to insert a key/data pair into the B+ tree.">insert</a>(InputIterator first, InputIterator last)
<a name="l00522"></a>00522     {
<a name="l00523"></a>00523         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a29d3aa8b03d2def35a358aebb2853053" title="Attempt to insert a key/data pair into the B+ tree.">insert</a>(first, last);
<a name="l00524"></a>00524     }
<a name="l00525"></a>00525 <span class="comment"></span>
<a name="l00526"></a>00526 <span class="comment">    /// Bulk load a sorted range [first,last). Loads items into leaves and</span>
<a name="l00527"></a>00527 <span class="comment">    /// constructs a B-tree above them. The tree must be empty when calling</span>
<a name="l00528"></a>00528 <span class="comment">    /// this function.</span>
<a name="l00529"></a>00529 <span class="comment"></span>    <span class="keyword">template</span> &lt;<span class="keyword">typename</span> Iterator&gt;
<a name="l00530"></a><a class="code" href="a00004.html#adb1b413f25e7d25afe782955aeafc66a">00530</a>     <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="a00004.html#adb1b413f25e7d25afe782955aeafc66a" title="Bulk load a sorted range [first,last).">bulk_load</a>(Iterator first, Iterator last)
<a name="l00531"></a>00531     {
<a name="l00532"></a>00532         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a053c808858d78e6f0a93041ab612d656" title="Bulk load a sorted range.">bulk_load</a>(first, last);
<a name="l00533"></a>00533     }
<a name="l00534"></a>00534 
<a name="l00535"></a>00535 <span class="keyword">public</span>:
<a name="l00536"></a>00536     <span class="comment">// *** Public Erase Functions</span>
<a name="l00537"></a>00537 <span class="comment"></span>
<a name="l00538"></a>00538 <span class="comment">    /// Erases the key/data pairs associated with the given key. For this</span>
<a name="l00539"></a>00539 <span class="comment">    /// unique-associative map there is no difference to erase().</span>
<a name="l00540"></a><a class="code" href="a00004.html#a4e44c51baca9a5959bacfe9f78fa3d44">00540</a> <span class="comment"></span>    <span class="keywordtype">bool</span> <a class="code" href="a00004.html#a4e44c51baca9a5959bacfe9f78fa3d44" title="Erases the key/data pairs associated with the given key.">erase_one</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a> &amp;key)
<a name="l00541"></a>00541     {
<a name="l00542"></a>00542         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a07ca3a19f1e20908f7cca3180420c817" title="Erases one (the first) of the key/data pairs associated with the given key.">erase_one</a>(key);
<a name="l00543"></a>00543     }
<a name="l00544"></a>00544 <span class="comment"></span>
<a name="l00545"></a>00545 <span class="comment">    /// Erases all the key/data pairs associated with the given key. This is</span>
<a name="l00546"></a>00546 <span class="comment">    /// implemented using erase_one().</span>
<a name="l00547"></a><a class="code" href="a00004.html#ad61de6ba3d5a99517d5b36e5024f8fe7">00547</a> <span class="comment"></span>    <a class="code" href="a00004.html#a4a2f9618a073d016e89cd8f1628caae1" title="Size type used to count keys.">size_type</a> <a class="code" href="a00004.html#ad61de6ba3d5a99517d5b36e5024f8fe7" title="Erases all the key/data pairs associated with the given key.">erase</a>(<span class="keyword">const</span> <a class="code" href="a00004.html#aa0687761c2d71344ad754a98a8650a92" title="First template parameter: The key type of the btree.">key_type</a> &amp;key)
<a name="l00548"></a>00548     {
<a name="l00549"></a>00549         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a8bced926ecf575a393e06ca7d35291f1" title="Erases all the key/data pairs associated with the given key.">erase</a>(key);
<a name="l00550"></a>00550     }
<a name="l00551"></a>00551 <span class="comment"></span>
<a name="l00552"></a>00552 <span class="comment">    /// Erase the key/data pair referenced by the iterator.</span>
<a name="l00553"></a><a class="code" href="a00004.html#a23f1f270183e77c1035b829081ebc8c9">00553</a> <span class="comment"></span>    <span class="keywordtype">void</span> <a class="code" href="a00004.html#ad61de6ba3d5a99517d5b36e5024f8fe7" title="Erases all the key/data pairs associated with the given key.">erase</a>(<a class="code" href="a00004.html#a2568bb45a7daa093f6e0c1869c693597" title="STL-like iterator object for B+ tree items.">iterator</a> iter)
<a name="l00554"></a>00554     {
<a name="l00555"></a>00555         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a8bced926ecf575a393e06ca7d35291f1" title="Erases all the key/data pairs associated with the given key.">erase</a>(iter);
<a name="l00556"></a>00556     }
<a name="l00557"></a>00557 
<a name="l00558"></a>00558 <span class="preprocessor">#ifdef BTREE_TODO</span>
<a name="l00559"></a>00559 <span class="preprocessor"></span><span class="comment">    /// Erase all key/data pairs in the range [first,last). This function is</span>
<a name="l00560"></a>00560 <span class="comment"></span><span class="comment">    /// currently not implemented by the B+ Tree.</span>
<a name="l00561"></a><a class="code" href="a00004.html#a99a3bccbdfef9c34596275e3da4da018">00561</a> <span class="comment"></span>    <span class="keywordtype">void</span> <a class="code" href="a00004.html#ad61de6ba3d5a99517d5b36e5024f8fe7" title="Erases all the key/data pairs associated with the given key.">erase</a>(<a class="code" href="a00004.html#a2568bb45a7daa093f6e0c1869c693597" title="STL-like iterator object for B+ tree items.">iterator</a> <span class="comment">/* first */</span>, <a class="code" href="a00004.html#a2568bb45a7daa093f6e0c1869c693597" title="STL-like iterator object for B+ tree items.">iterator</a> <span class="comment">/* last */</span>)
<a name="l00562"></a>00562     {
<a name="l00563"></a>00563         abort();
<a name="l00564"></a>00564     }
<a name="l00565"></a>00565 <span class="preprocessor">#endif</span>
<a name="l00566"></a>00566 <span class="preprocessor"></span>
<a name="l00567"></a>00567 <span class="preprocessor">#ifdef BTREE_DEBUG</span>
<a name="l00568"></a>00568 <span class="preprocessor"></span><span class="keyword">public</span>:
<a name="l00569"></a>00569     <span class="comment">// *** Debug Printing</span>
<a name="l00570"></a>00570 <span class="comment"></span>
<a name="l00571"></a>00571 <span class="comment">    /// Print out the B+ tree structure with keys onto the given ostream. This function</span>
<a name="l00572"></a>00572 <span class="comment">    /// requires that the header is compiled with BTREE_DEBUG and that key_type</span>
<a name="l00573"></a>00573 <span class="comment">    /// is printable via std::ostream.</span>
<a name="l00574"></a><a class="code" href="a00004.html#a2ca47ab7ffcd8ee2940c3fdd8690d002">00574</a> <span class="comment"></span>    <span class="keywordtype">void</span> <a class="code" href="a00004.html#a2ca47ab7ffcd8ee2940c3fdd8690d002" title="Print out the B+ tree structure with keys onto the given ostream.">print</a>(std::ostream &amp;os)<span class="keyword"> const</span>
<a name="l00575"></a>00575 <span class="keyword">    </span>{
<a name="l00576"></a>00576         <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a29af931b81dc3446d1ffadab6fd5e017" title="Print out the B+ tree structure with keys onto the given ostream.">print</a>(os);
<a name="l00577"></a>00577     }
<a name="l00578"></a>00578 <span class="comment"></span>
<a name="l00579"></a>00579 <span class="comment">    /// Print out only the leaves via the double linked list.</span>
<a name="l00580"></a><a class="code" href="a00004.html#a0170dc9ca200e9e7a91d7a311b22ef0c">00580</a> <span class="comment"></span>    <span class="keywordtype">void</span> <a class="code" href="a00004.html#a0170dc9ca200e9e7a91d7a311b22ef0c" title="Print out only the leaves via the double linked list.">print_leaves</a>(std::ostream &amp;os)<span class="keyword"> const</span>
<a name="l00581"></a>00581 <span class="keyword">    </span>{
<a name="l00582"></a>00582         <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#a2e9097d4266851d84d9e3813921155c6" title="Print out only the leaves via the double linked list.">print_leaves</a>(os);
<a name="l00583"></a>00583     }
<a name="l00584"></a>00584 <span class="preprocessor">#endif</span>
<a name="l00585"></a>00585 <span class="preprocessor"></span>
<a name="l00586"></a>00586 <span class="keyword">public</span>:
<a name="l00587"></a>00587     <span class="comment">// *** Verification of B+ Tree Invariants</span>
<a name="l00588"></a>00588 <span class="comment"></span>
<a name="l00589"></a>00589 <span class="comment">    /// Run a thorough verification of all B+ tree invariants. The program</span>
<a name="l00590"></a>00590 <span class="comment">    /// aborts via BTREE_ASSERT() if something is wrong.</span>
<a name="l00591"></a><a class="code" href="a00004.html#a5001888f16d9f8fdc634cec05c67f961">00591</a> <span class="comment"></span>    <span class="keywordtype">void</span> <a class="code" href="a00004.html#a5001888f16d9f8fdc634cec05c67f961" title="Run a thorough verification of all B+ tree invariants.">verify</a>()<span class="keyword"> const</span>
<a name="l00592"></a>00592 <span class="keyword">    </span>{
<a name="l00593"></a>00593         <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#ad7008114b409fe53a5739a69f3b90e59" title="Run a thorough verification of all B+ tree invariants.">verify</a>();
<a name="l00594"></a>00594     }
<a name="l00595"></a>00595 
<a name="l00596"></a>00596 <span class="keyword">public</span>:
<a name="l00597"></a>00597 <span class="comment"></span>
<a name="l00598"></a>00598 <span class="comment">    /// Dump the contents of the B+ tree out onto an ostream as a binary</span>
<a name="l00599"></a>00599 <span class="comment">    /// image. The image contains memory pointers which will be fixed when the</span>
<a name="l00600"></a>00600 <span class="comment">    /// image is restored. For this to work your key_type and data_type must be</span>
<a name="l00601"></a>00601 <span class="comment">    /// integral types and contain no pointers or references.</span>
<a name="l00602"></a><a class="code" href="a00004.html#a8794673d23f9ae4525d84dc01f651309">00602</a> <span class="comment"></span>    <span class="keywordtype">void</span> <a class="code" href="a00004.html#a8794673d23f9ae4525d84dc01f651309" title="Dump the contents of the B+ tree out onto an ostream as a binary image.">dump</a>(std::ostream &amp;os)<span class="keyword"> const</span>
<a name="l00603"></a>00603 <span class="keyword">    </span>{
<a name="l00604"></a>00604         <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#af26da2c6a1723bd3c98229b3670e2d28" title="Dump the contents of the B+ tree out onto an ostream as a binary image.">dump</a>(os);
<a name="l00605"></a>00605     }
<a name="l00606"></a>00606 <span class="comment"></span>
<a name="l00607"></a>00607 <span class="comment">    /// Restore a binary image of a dumped B+ tree from an istream. The B+ tree</span>
<a name="l00608"></a>00608 <span class="comment">    /// pointers are fixed using the dump order. For dump and restore to work</span>
<a name="l00609"></a>00609 <span class="comment">    /// your key_type and data_type must be integral types and contain no</span>
<a name="l00610"></a>00610 <span class="comment">    /// pointers or references. Returns true if the restore was successful.</span>
<a name="l00611"></a><a class="code" href="a00004.html#a40d04b8ae97fae9e0a91d75f022a8000">00611</a> <span class="comment"></span>    <span class="keywordtype">bool</span> <a class="code" href="a00004.html#a40d04b8ae97fae9e0a91d75f022a8000" title="Restore a binary image of a dumped B+ tree from an istream.">restore</a>(std::istream &amp;is)
<a name="l00612"></a>00612     {
<a name="l00613"></a>00613         <span class="keywordflow">return</span> <a class="code" href="a00004.html#a71462634691fd4ab38cde89991dd8d69" title="The contained implementation object.">tree</a>.<a class="code" href="a00001.html#adf438d8a86c9784e277adfbb6ed5783d" title="Restore a binary image of a dumped B+ tree from an istream.">restore</a>(is);
<a name="l00614"></a>00614     }
<a name="l00615"></a>00615 };
<a name="l00616"></a>00616 
<a name="l00617"></a>00617 } <span class="comment">// namespace stx</span>
<a name="l00618"></a>00618 
<a name="l00619"></a>00619 <span class="preprocessor">#endif // _STX_BTREE_MAP_H_</span>
</pre></div></div><!-- contents -->
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Classes</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Namespaces</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&#160;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark">&#160;</span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark">&#160;</span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(8)"><span class="SelectionMark">&#160;</span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(9)"><span class="SelectionMark">&#160;</span>Friends</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(10)"><span class="SelectionMark">&#160;</span>Defines</a></div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>



<hr class="footer"/><address class="footer"><small>
Generated on Sun May 5 2013 23:38:43 for STX B+ Tree Template Classes by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.7.6.1
</small></address>

</body>
</html>
